// 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
// 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
// 输入: `[ [1,2], [2,3], [3,4], [1,3] ]`
// 输出: 1
// 解释: 移除 `[1,3]` 后，剩下的区间没有重叠。
// 思路1，贪心
// 右边界排序，寻找最多非重叠区间，结果
function eraseOverlapIntervals(intervals) {
    intervals.sort((a, b) => a[1] - b[1])
    let count = 1
    let end = intervals[0][1]
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= end) {
            count++
            end = intervals[i][1]
        }        
    }
    return intervals.length - count
}

console.log(eraseOverlapIntervals([ [1,2], [2,3], [3,4], [1,3] ]))

// 思路2，左边界排序
function eraseOverlapIntervals2(intervals) {
    intervals.sort((a, b) => a[0] - b[0])
    let count = 0
    let minRight = intervals[0][1]
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < minRight) {
            count++
            // 尽可能选取小的
            minRight = Math.min(minRight, intervals[i][1])
        } else {
            minRight = intervals[i][1]
        }
    }
    return count
}
console.log(eraseOverlapIntervals2([ [1,2], [2,3], [3,4], [1,3] ]))